package com.xh.clean.collection;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * linkedList Demo
 *最近在做图像处理的时候，发现某一段代码非常的慢，慢得让人无法接受。主要的代码是顺序访问一个LinkedList的元素，
 * 效果是随着index的变大，速度越来越慢，list的元素个数在百万以上。找到原因，分享出来，也希望大家不要跳入同一个陷阱。
 * 还是那一句话，可运行的代码和高质量的代码之间还是有比较远的距离。
 * @author 杨杰
 * @create 2018-08-31 10:11
 **/
public class LinkedListDemo {
    public static void main(String[] args) {
        int size = 2000000;
        List<String> list = new LinkedList<String>();
        for (int i = 0; i < size; i++) {
            list.add("Just some test data");
        }
        /**
         * 错误原因
         * 错误的代码就是list.get(i)，LinkedList的底层是一个链表，随机访问i的时候，链表只能从头往后数，第i个才返回。所以时间随着i的变大时间会越来越长。
         */
        long startTime = System.currentTimeMillis();
//        for (int i = 0; i < size; i++) {
//            list.get(i);
//            if (i % 10000 == 0) {
//                System.out.println("query 10000 elements spend: "
//                        + (System.currentTimeMillis() - startTime));
//                startTime = System.currentTimeMillis();
//            }
//        }
        /**
         * 正确用法
         * 顺序访问，LinkedList绝对不要用get方法，即使LinkedList的元素个数只有很少的几个。养成好习惯，免得犯错。
         */
        int i = 0;
        for (String s:list) {
            i++;
            if (i % 10000 == 0) {
                System.out.println("query 10000 elements spend: "
                        + (System.currentTimeMillis() - startTime));
                startTime = System.currentTimeMillis();
            }
        }
    }

    /**
     * 测试ArrayList 增删改效率
     */
    @Test
    public void testAL() {
        // add elements
        int size = 20000000;
        List<String> list = new ArrayList<String>();
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add("Just some test data");
        }
        System.out.println("add " + size + " elements spend: "
                + (System.currentTimeMillis() - startTime));

        // query
        startTime = System.currentTimeMillis();
        String median = list.get(size / 2);
        System.out.println("query median spend: "
                + (System.currentTimeMillis() - startTime));

        // delete
        startTime = System.currentTimeMillis();
        list.remove(median);
        System.out.println("delete median spend: "
                + (System.currentTimeMillis() - startTime));
    }

    /**
     * 测试LinkedList 增删改效率
     */
    @Test
    public void testLL() {
        // add elements
        int size = 20000000;
        List<String> list = new LinkedList<String>();
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add("Just some test data");
        }
        System.out.println("add " + size + " elements spend: "
                + (System.currentTimeMillis() - startTime));

        // query
        startTime = System.currentTimeMillis();
        String median = list.get(size / 2);
        System.out.println("query median spend: "
                + (System.currentTimeMillis() - startTime));

        // delete
        startTime = System.currentTimeMillis();
        list.remove(median);
        System.out.println("delete median spend: "
                + (System.currentTimeMillis() - startTime));
    }
}
